package br.com.rookgraph.articulacoes;

import br.com.rookgraph.Graph;

public class ProcessadorArticulacoes {

	private static final int BRANCO = 0;
	private static final int CINZA = 1;
	private static final int PRETO = 2;
	
	private static int maxn;
	
	private static int[] cor; // BRANCO se o vértice i não foi encontrado pela busca em profundidade,
                              // CINZA se  foi visitado pela busca em profundidade
                              // PRETO se todos os vértices adjacentes ao vértice i foram visitados
	
	private static int[] articulacoes; // articulacoes[i] é igual a 1 se o vértice i é uma articulação e 0 em caso contrário
	private static int[] nivel; // nivel[i] é a ordem do vértice i na busca em profundidade
	private static int[] pai; // pai[i] representa o vértice predecessor na busca em profundidade
	private static int[] menor;
	private static int cont;
	

	public static int[] identificarArticulacoes(Graph graph, int root) {
		inicializarVariaveis(graph);
		
		depthFirstSearch(root, graph);
		
		return articulacoes;
	}
	
	private static void inicializarVariaveis(Graph graph) {
		maxn = graph.order + 1;
		articulacoes = new int[maxn];
		cor = new int[maxn];
		nivel = new int[maxn];
		pai = new int[maxn];
		menor = new int[maxn];
		cont = 1;
		
		for (int z = 0; z < maxn; z++) {
			cor[z] = BRANCO;
			pai[z] = z;
			articulacoes[z] = 0;
		}
	}

	private static void depthFirstSearch(int v, Graph graph) {
		int j, u, nfilhos;
		cor[v] = CINZA;
		menor[v] = cont++;
		nivel[v] = menor[v];
		nfilhos = 0;
		
		// Vetor com os vértices adjacentes ao vértice 'v'
		int[] adj = graph.getAdjacentes(v);
		
		// Laço para percorrer vértices adjacentes a 'v'
		for (j = 0; j < adj.length; j++) {
			// variável 'u' guarda o j-ésimo vértice adjacente a 'v'
			u = adj[j];
			
			if (cor[u] == BRANCO) {
				// Se o vértice u for BRANCO, deve ser processado
				nfilhos++;
				pai[u] = v;
				depthFirstSearch(u, graph);
				
				if (menor[u] < menor[v]) {
					menor[v] = menor[u];
				}
				
				if (nivel[v] != 1 && menor[u] >= nivel[v]) {
					articulacoes[v] = 1;
				}
			} else if (cor[u] == CINZA && pai[v] != u) {
				// Se o vérfice 'u' for cinza e ele não for o pai de 'v', então nível de 'v' deve ser atualizado
				if (nivel[u] < nivel[v]) {
					menor[v] = nivel[u];
				}
			}
		}
		
		// Marcar articulação segundo condições
		if (nivel[v] == 1 && nfilhos > 2) {
			articulacoes[v] = 1;
		}
		
		if (articulacoes[v] == 1) {
			int numGrafosDesconexos = contarGrafosDesconexos(v, graph);
			
			// Se a remoção da articulação 'v' cria menos de 3 partes desconexas no grafo, desconsiderar esta articulação 
			if (numGrafosDesconexos < 3) {
				articulacoes[v] = 0;
			}
		}
		
		// Marcar vértice 'v' como tendo todos os vértice adjacentes visitados
		cor[v] = PRETO;
	}
	
	private static int contarGrafosDesconexos(int v, Graph graph) {
		int numGrafos = 0;
		
		try {
			int[] adj = graph.getAdjacentes(v);
			int[] visitado = new int[maxn];
			for (int i = 0; i < maxn; i++) visitado[i] = BRANCO;
			
			numGrafos = adj.length;
			
			Graph clone = (Graph) graph.clone();
			clone.removeNode(v-1);
			
			// Para cada vértice adjacente ao vértice 'v', listar os alcançáveis e marcá-los
			for (int i = 0; i < adj.length; i++) {
				// Recupera a lista de vértices no grafo 'clone' que se conegue alcançar a partir do vértice adj[i]
				int[] alcancaveis = clone.reached(adj[i], new int[maxn]);
				
				// Verificar se os vértices alcançáveis a partir de adj[i] já foi alcançado anteriormente.
				// Em caso positivo, 1 bloco desconexo a menos na contagem (numGrafos).
				for (int j = 0; j < alcancaveis.length; j++) {
					if (visitado[alcancaveis[j]] == CINZA) {
						numGrafos--;
						break;
					}
				}
				
				// Marcar como visitados os vértices alcançáveis a partir de adj[i]
				for (int j = 0; j < alcancaveis.length; j++) {
					visitado[alcancaveis[j]] = CINZA;
				}
			}
		} catch (CloneNotSupportedException e) {
			e.printStackTrace();
		}
		
		return numGrafos;
	}

	public static void main(String[] args) {
		Graph graph = inicializarGrafo();
		identificarArticulacoes(graph, 1);
		
		System.out.println(graph + "\n");
		
		mostraVetor(new int[]{0,1,2,3,4,5,6,7,8});
		mostraVetor(articulacoes);
	}

	private static void mostraVetor(int[] vet) {
		for (int i = 0; i < maxn; i++) {
			System.out.print(vet[i]);
			if (i < maxn - 1) System.out.print(", ");
		}
		System.out.println();
	}

	private static Graph inicializarGrafo() {
		Graph g = new Graph(8);
		g.edges()[0][2] = 1;
		g.edges()[2][0] = 1;
		g.edges()[0][3] = 1;
		g.edges()[3][0] = 1;
		g.edges()[3][1] = 1;
		g.edges()[1][3] = 1;
//		g.edges()[3][2] = 1;
//		g.edges()[2][3] = 1;
		g.edges()[5][1] = 1;
		g.edges()[1][5] = 1;
		g.edges()[6][1] = 1;
		g.edges()[1][6] = 1;
		g.edges()[6][4] = 1;
		g.edges()[4][6] = 1;
		g.edges()[2][5] = 1;
		g.edges()[5][2] = 1;
//		g.edges()[5][6] = 1;
//		g.edges()[6][5] = 1;
		g.edges()[1][7] = 1;
		g.edges()[7][1] = 1;
		
		return g;
	}
	
}
